package com.idig8.leetcode.链表;

public class _206_反转链表 {

    public class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    /**
     * 递归方式
     *
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {

        if (head == null) return null;
        if (head.next == null) return head;

        ListNode newhead = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return newhead;
    }


    /**
     * 非递归的方式
     *
     * @param head
     * @return
     */
    public ListNode reverseList2(ListNode head) {

        if (head == null) return null;
        if (head.next == null) return head;

        ListNode newhead = null;
        while (head != null) {
            ListNode tmp = head.next;
            head.next = newhead;
            newhead = head;
            head = tmp;

        }
        return newhead;
    }
}
